package DataStructure.graph;

public class DirectedCycle {
    private boolean[] marked;
    private boolean hasCycle;
    private boolean[] onStack;

    public DirectedCycle(Digraph G){
        this.marked=new boolean[G.V()];
        this.hasCycle=false;
        this.onStack=new boolean[G.V()];

        //找到图中每一个顶点，让每一个顶点作为入口调用一次dfs进行搜索
        for (int v = 0; v < G.V(); v++) {
            //如果当前顶点还没有被搜索过则调用dfs搜索
            if(!marked[v]){
                dfs(G, v);
            }
        }

    }

    //基于深度优先搜索检测图中是否有环
    public void dfs(Digraph G,int v){
        marked[v]=true;
        //把当前顶点进栈
        onStack[v]=true;
        //进行深度搜索
        for (Integer w : G.adj(v)) {
            //如果w没有被搜索过
            if(!marked[w]){
                dfs(G,w);
            }
            //判断当前顶点w是否已经在栈中，如果已经在栈中，证明当前顶点之前处于搜索的状态，证明检测到环了
            if(onStack[w]){
                hasCycle=true;
                return;
            }
        }
        //把当前顶点出栈
        onStack[v]=false;
    }

    //判断当前G中是否有环
    public boolean hasCycle(){
        return hasCycle;
    }
}
